// LCR 019. 验证回文串 II
class Solution {
public:
    bool check(string& s, int left, int right)
    {
        while(left < right)
        {
            if(s[left++] != s[right--]) return false;
        }
        return true;
    }

    bool validPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while(left < right)
        {
            if(s[left] == s[right])
            {
                ++left;
                --right;
            }
            else
            {
                return check(s, left+1, right) || check(s, left, right-1);
            }
        }
        return true;
    }
};

// LCR 072. x 的平方根
class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x, ret = 0;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if((long long)mid * mid <= x)
            {
                ret = mid;
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return ret;
    }
};